import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        char[][] grid1 = {
                {'1'},
                {'1'}
        };
        System.out.println(s.numIslands(grid1));
    }

    public int numIslands(char[][] grid) {
        /**
         * 岛屿数量
         *  本质就是计算连通块的数量
         *  解题思路：
         *      使用并查集对相邻元素进行合并，最后计算集合个数即可
         *      <1> 计算数组中1的个数 ==> 为了计算集合数量
         *      <2> 每次查看上、左元素 ==> 因为下、右会由遍历纳入
         *      <3> */
        // 1 预处理
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    count ++;
                }
            }
        }
        // -初始化
        initialize(m * n);

        // 2 遍历元素
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1') {
                    // -计算编号，后续使用编号对并查集进行操作
                    int lastUp = (i-1) * n + j;
                    int lastLeft = i * n + j - 1;
                    int current = i * n + j;
                    if(i != 0 && grid[i-1][j] == '1') {
                        union(lastUp, current);
                        count --;
                    }
                    // -第二次合并前需要判断是否上面已经合并，不判断会导致集合数量计算错误
                    if(j != 0 && grid[i][j-1] == '1' && !isSameSet(lastLeft, current)) {
                        union(lastLeft, current);
                        count --;
                    }
                }
            }
        }

        // 3 返回值
        return count;
    }

    // 并查集实现
    public static int MAX_N = 0;
    public static int[] father;
    public static int[] size;
    public static int[] stack;

    public static void initialize(int n) {
        /**
         * 初始化并查集*/
        // 1 分配空间
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];

        // 2 初始化
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到目标元素a所在集合的代表元素，并作扁平化处理*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处在同一集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合*/
        int fa = find(a);
        int fb = find(b);

        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                father[fa] = fb;
            }
        }
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        /**
         * 迷宫中离入口最近的出口
         *  bfs单源最短路问题
         *  */
        // 1 初始化
        int m = maze.length;
        int n = maze[0].length;
        // -记录距离
        int distance = 0;
        // -记录遍历痕迹
        int[][] record = new int[m][n];
        // -准备队列并初始化
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrance);
        record[entrance[0]][entrance[1]] = 1;
        // -准备下标矩阵
        int[][] indexArray = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};

        // 2 bfs搜索
        while(!queue.isEmpty()) {
            // -每次向外拓展一层
            int curSize = queue.size();
            for(int i = 0; i < curSize; i++) {
                int[] cur = queue.poll();
                for(int[] e: indexArray) {
                    int x = cur[0] + e[0];
                    int y = cur[1] + e[1];
                    // -搜索到未遍历过的路径则入队
                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && record[x][y] == 0) {
                        queue.offer(new int[]{x, y});
                        record[x][y] = 1;
                        // -判断当前路径是否是出口
                        if(x == 0 || x == m-1 || y == 0 || y == n-1) {
                            return distance + 1;
                        }
                    }
                }
            }
            // -遍历完一层，距离+1
            distance ++;
        }

        // 3 返回值
        return -1;
    }
}












